package leetcode.pre100;


import utils.ListNode;

/**
 * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->1->2
 * 输出: 1->2
 * 示例 2:
 * <p>
 * 输入: 1->1->2->3->3
 * 输出: 1->2->3
 * <p>
 * 删除重复的节点1：{1,2,2,3,4,4,5} ->{1,2,3,4,5}
 * {@link leetcode.a_总结分布.Code12_链表问题}
 * <p>
 * {@link baseclass.d_list.Code12_FindKNodeFromTailInList_DeleteKNodeFromTail}
 * <p>
 * {@link baseclass.d_list.Code11_DeleteRepeatNode}
 *
 * <p>
 * {@link baseclass.d_list.Code11_DeleteRepeatNode2_删除所有重复节点}
 *
 * @date 2020/2/28 22:39
 */
public class Code82_DeleteRepeatNode_删除链表重复元素1 {
    public static ListNode deleteRepeat1(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = head;
        ListNode after = head.next;
        while (after != null) {
            ListNode next = after.next;
            //删除after
            if (pre.val == after.val) {
                pre.next = next;
                after.next = null;
            } else {
                //更新pre
                pre = after;
            }
            after = next;
        }
        return head;
    }

    public static ListNode deleteRepeat2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = head;
        ListNode after = head.next;
        while (after != null) {
            //考虑after == null  1,2,2  pre = 2
            while (after != null && after.val == pre.val) {
                after = after.next;
            }
            //pre - after一直相等，且after来到了null
            if (after == null) {
                pre.next = null;
                break;
            }
            //after.val != pre.val
            pre.next = after;
            pre = pre.next;
            after = after.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        pHead.next = new ListNode(1);
        pHead.next.next = new ListNode(2);
        pHead.next.next.next = new ListNode(3);
        pHead.next.next.next.next = new ListNode(3);
        deleteRepeat2(pHead);
        while (pHead != null) {
            System.out.print(pHead.val + " ");
            pHead = pHead.next;
        }
    }

}
